{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove All Adjacent Duplicates In String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeDuplicates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除字符串中的所有相邻重复项"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出由小写字母组成的字符串&nbsp;<code>S</code>，<strong>重复项删除操作</strong>会选择两个相邻且相同的字母，并删除它们。</p>\n",
    "\n",
    "<p>在 S 上反复执行重复项删除操作，直到无法继续删除。</p>\n",
    "\n",
    "<p>在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;abbaca&quot;\n",
    "<strong>输出：</strong>&quot;ca&quot;\n",
    "<strong>解释：</strong>\n",
    "例如，在 &quot;abbaca&quot; 中，我们可以删除 &quot;bb&quot; 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 &quot;aaca&quot;，其中又只有 &quot;aa&quot; 可以执行重复项删除操作，所以最后的字符串为 &quot;ca&quot;。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= S.length &lt;= 20000</code></li>\n",
    "\t<li><code>S</code> 仅由小写英文字母组成。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-all-adjacent-duplicates-in-string](https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-all-adjacent-duplicates-in-string](https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abbaca\"', '\"azxxzy\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from dataclasses import dataclass\n",
    "from typing import List\n",
    "\n",
    "@dataclass\n",
    "class LetterCount:\n",
    "    letter: str\n",
    "    count: int\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack: List[LetterCount] = []\n",
    "\n",
    "        for letter in s:\n",
    "            if len(stack) == 0 or letter != stack[-1].letter:\n",
    "                stack.append(LetterCount(letter, 1))\n",
    "            elif stack[-1].count < k - 1:\n",
    "                stack[-1].count += 1\n",
    "            else:\n",
    "                stack.pop()\n",
    "\n",
    "        return \"\".join(lc.letter * lc.count for lc in stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        if len(s) < 2:\n",
    "            return s\n",
    "\n",
    "        tmp_s=s\n",
    "        while True:\n",
    "            char_list=[]\n",
    "            count_list = []\n",
    "            count=0\n",
    "            for s_idx in tmp_s:\n",
    "                if len(char_list) == 0  or s_idx != char_list[-1]:\n",
    "                    char_list.append(s_idx)\n",
    "                    count_list.append(1)\n",
    "                else:\n",
    "                    count_list[-1] +=1\n",
    "            tmp_s=\"\"\n",
    "            is_end = True\n",
    "            for i in range(len(char_list)):\n",
    "                if count_list[i] % k >0:\n",
    "                    tmp_s=tmp_s+char_list[i] *(count_list[i]%k)\n",
    "                else:\n",
    "                    is_end = False\n",
    "            print(tmp_s)\n",
    "            if is_end:\n",
    "                break\n",
    "            \n",
    "\n",
    "        return tmp_s        \n",
    "\n",
    "                    \n",
    "                \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        a = []\n",
    "        b = []\n",
    "        tmp_num = 1\n",
    "        for i in s:\n",
    "            if a and a[-1] == i:\n",
    "                tmp_num += 1\n",
    "            else:\n",
    "                if a:\n",
    "                    b.append(tmp_num)\n",
    "                tmp_num = 1\n",
    "            if tmp_num == k:\n",
    "                for j in range(k-1):\n",
    "                    a.pop()\n",
    "                if b:\n",
    "                    tmp_num = b.pop()\n",
    "                else:\n",
    "                    tmp_num = 1\n",
    "\n",
    "            else:\n",
    "                a.append(i)\n",
    "\n",
    "        return \"\".join(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack = []\n",
    "        stack_count = []\n",
    "\n",
    "        for i, char in enumerate(s):\n",
    "            if len(stack) == 0:\n",
    "                stack.append(char)\n",
    "                print(stack)\n",
    "                stack_count.append(1)\n",
    "                continue\n",
    "            if char != stack[-1]:\n",
    "                stack.append(char)\n",
    "                stack_count.append(1)\n",
    "            else:\n",
    "                if stack_count[-1] < k - 1:\n",
    "                    stack.append(char)\n",
    "                    stack_count[-1] += 1 \n",
    "                else:\n",
    "                    for _ in range(k - 1):\n",
    "                        stack.pop()\n",
    "                    stack_count.pop()\n",
    "        string = \"\"\n",
    "        for c in stack:\n",
    "            string += c \n",
    "        return string\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack = []\n",
    "        \n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if not stack or s[i-1] != s[i]:\n",
    "                stack.append(1)\n",
    "            else:\n",
    "                stack[-1] += 1\n",
    "                if stack[-1] == k:\n",
    "                    stack.pop()\n",
    "                    s = s[:i-k+1] + s[i+1:]\n",
    "                    i = i - k\n",
    "            i += 1\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        flag=1\n",
    "        helper='abcdefghijklmnopqrstuvwxyz'\n",
    "        while flag:\n",
    "            flag=0\n",
    "            for c in helper:\n",
    "                if c*k in s:\n",
    "                    s=s.replace(c*k,'')\n",
    "                    flag=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        while True:\n",
    "            flag = False\n",
    "            for i in string.ascii_lowercase:\n",
    "                substr = i*k\n",
    "                news = s.replace(substr,\"\")\n",
    "                if news!=s:\n",
    "                    flag = True\n",
    "                    s = news\n",
    "                    break\n",
    "            if not flag :\n",
    "                break\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack = ''\n",
    "        for c in s:\n",
    "            if not stack or stack[-1] != c:\n",
    "                stack += c\n",
    "            else:\n",
    "                if stack.endswith(c * (k - 1)):\n",
    "                    stack = stack[:-(k - 1)]\n",
    "                else:\n",
    "                    stack += c\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        res = ''\n",
    "        for x in s:\n",
    "            if res[-k+1:] == x * (k-1):\n",
    "                res = res[:-k+1]\n",
    "            else:\n",
    "                res += x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        i, j = 0, k\n",
    "        while i < len(s):\n",
    "            if len(s) < k:\n",
    "                break\n",
    "            elif s[i:j].count(s[i]) == k:\n",
    "                s = s[:i] + s[j:]\n",
    "                i -= k\n",
    "                j -= k\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if i == 0 or s[i] != s[i - 1]:\n",
    "                stack.append(1)\n",
    "            else:\n",
    "                cnt = stack.pop() + 1\n",
    "                if cnt == k:\n",
    "                    s = s[:i - k + 1] + s[i + 1:]\n",
    "                    i -= k\n",
    "                    n -= k\n",
    "                else:\n",
    "                    stack.append(cnt)\n",
    "            i += 1\n",
    "        return s\n",
    "\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k:int) -> str:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if stack and stack[-1] == i:\n",
    "                stack.append(i)\n",
    "                count += 1\n",
    "                if count == k:\n",
    "                    while count:\n",
    "                        stack.pop()\n",
    "                        count -= 1\n",
    "                    count, j = 1, len(stack)\n",
    "                    m = 2\n",
    "                    while j > 1:\n",
    "                        if stack[-1] == stack[-m]:\n",
    "                            count += 1\n",
    "                            m += 1\n",
    "                            j -= 1\n",
    "                        else:\n",
    "                            break\n",
    "            else:\n",
    "                stack.append(i)\n",
    "                count = 1\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"method 1\"\n",
    "    def rewind(self, s: str, p: int) -> int:\n",
    "        p2 = p\n",
    "        while p2 > 0:\n",
    "            p2 -= 1\n",
    "            if s[p2] != s[p]:\n",
    "                return p2\n",
    "        return p2\n",
    "\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        # 祖玛！？\n",
    "\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "\n",
    "        while p1 < len(s):\n",
    "            p2 += 1\n",
    "\n",
    "            if p2 - p1 >= k:\n",
    "                s = s.replace(s[p1 : p2], \"\")\n",
    "                if p1 >= len(s):\n",
    "                    break\n",
    "                p1 = self.rewind(s, p1)\n",
    "                p2 = p1\n",
    "            \n",
    "            if p2 >= len(s):\n",
    "                break\n",
    "            \n",
    "            if s[p1] != s[p2]:\n",
    "                p1 = p2\n",
    "\n",
    "        return s\n",
    "\n",
    "    \"method 2\"\n",
    "    # def removeDuplicates(self, s: str, k: int) -> str:\n",
    "    #     repeat = []\n",
    "    #     length = 1\n",
    "    #     for i in range(1, len(s)):\n",
    "    #         if s[i] != s[i - 1]:\n",
    "    #             repeat.append([s[i - 1], length])\n",
    "    #             length = 1\n",
    "    #             continue\n",
    "    #         length += 1\n",
    "    #     repeat.append([s[-1], length])\n",
    "    #     i = 0\n",
    "    #     while i < len(repeat):\n",
    "    #         if repeat[i][1] >= k:\n",
    "    #             repeat[i][1] = repeat[i][1] % k\n",
    "    #             if repeat[i][1] == 0:\n",
    "    #                 repeat.pop(i)\n",
    "    #                 if i >= len(repeat):\n",
    "    #                     break\n",
    "    #                 if i == 0:\n",
    "    #                     continue\n",
    "    #                 if repeat[i - 1][0] != repeat[i][0]:\n",
    "    #                     continue\n",
    "    #                 # else 两边 same char\n",
    "    #                 repeat[i - 1][1] += repeat[i][1]\n",
    "    #                 repeat.pop(i)\n",
    "    #                 i -= 1\n",
    "    #                 continue\n",
    "    #         i += 1\n",
    "\n",
    "    #     s = \"\"\n",
    "    #     for item in repeat:\n",
    "    #         s += item[0] * item[1]\n",
    "\n",
    "    #     return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack = list()\n",
    "\n",
    "        for current in range(len(s)):\n",
    "            if not stack or stack[-1][0] != s[current]:\n",
    "                stack.append(s[current])\n",
    "            else:\n",
    "                stack[-1] += s[current]\n",
    "            if len(stack[-1]) == k:\n",
    "                stack.pop()\n",
    "        \n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "\n",
    "        stack = [s[0]]\n",
    "        n = len(s)\n",
    "        stackNum = [1]\n",
    "        \n",
    "        for i  in range(1,n):\n",
    "            \n",
    "            if stack and stack[-1] == s[i]:\n",
    "                stackNum[-1] += 1\n",
    "            else:\n",
    "                stackNum.append(1)\n",
    "            stack.append(s[i])\n",
    "\n",
    "            if stackNum[-1] == k:\n",
    "                num = stackNum[-1]\n",
    "                while num > 0:\n",
    "                    stack.pop()\n",
    "                    num -= 1\n",
    "                stackNum.pop()\n",
    "        \n",
    "        # print(stackNum)\n",
    "        return \"\".join(stack)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "\n",
    "        stack = [s[0]]\n",
    "        n = len(s)\n",
    "        stackNum = [1]\n",
    "        \n",
    "        for i  in range(1,n):\n",
    "            \n",
    "            if stack and stack[-1] == s[i]:\n",
    "                stackNum[-1] += 1\n",
    "            else:\n",
    "                stackNum.append(1)\n",
    "            stack.append(s[i])\n",
    "            \n",
    "            if stackNum[-1] == k:\n",
    "                num = stackNum[-1]\n",
    "                while num > 0:\n",
    "                    stack.pop()\n",
    "                    num -= 1\n",
    "                stackNum.pop()\n",
    "        \n",
    "        print(stackNum)\n",
    "        return \"\".join(stack)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack=[]\n",
    "        xl=[]\n",
    "        x=0\n",
    "        for i in range(len(s)):\n",
    "            if len(stack)==0 or stack[-1]==s[i]:\n",
    "                x+=1\n",
    "            else:\n",
    "                xl.append(x)\n",
    "                x=1\n",
    "            stack.append(s[i])\n",
    "            if x==k:\n",
    "                stack=stack[:-1*k]\n",
    "                if len(stack)==0:\n",
    "                    x=0\n",
    "                else:\n",
    "                    x=xl[-1]\n",
    "                    xl.pop()\n",
    "            # print(x,stack,xl)\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        counts = []\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if not stack or stack[-1] != s[i]:\n",
    "                counts.append(1)\n",
    "                stack.append(s[i])\n",
    "            else:\n",
    "                counts[-1] += 1\n",
    "                stack.append(s[i])\n",
    "                if counts[-1] == k:\n",
    "                    counts.pop()\n",
    "                    stack = stack[:-k]\n",
    "            \n",
    "        return ''.join(stack)            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        chars, count = list(s), []\n",
    "        slow = fast = 0\n",
    "        while fast < len(s):\n",
    "            chars[slow] = chars[fast]\n",
    "            if slow == 0 or chars[slow] != chars[slow - 1]:\n",
    "                count.append(1)\n",
    "            else:\n",
    "                increat = count.pop() + 1\n",
    "                if increat == k:\n",
    "                    slow = slow - k\n",
    "                else:\n",
    "                    count.append(increat)\n",
    "            slow += 1\n",
    "            fast += 1\n",
    "        return \"\".join(chars[0:slow])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stk = []\n",
    "        cnt = 0\n",
    "        cur = \"\"\n",
    "        for x in s:\n",
    "            if cur == x:\n",
    "                cnt += 1\n",
    "                cnt %= k\n",
    "            else:\n",
    "                if cnt == 0 and stk and stk[-1][1] == x:\n",
    "                    cnt0, _ = stk[-1]\n",
    "                    stk.pop()\n",
    "                    cur = x\n",
    "                    cnt = cnt0 + 1\n",
    "                    cnt %= k\n",
    "                else:\n",
    "                    if cnt > 0:\n",
    "                        stk.append((cnt, cur))\n",
    "                    cur = x\n",
    "                    cnt = 1\n",
    "            # print(stk, cur, cnt)\n",
    "        if cnt > 0:\n",
    "            stk.append((cnt, cur))\n",
    "        ans = [x * y for x, y in stk]\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        # 贪心思想\n",
    "        # 利用栈 + hash存储栈内某个字符的个数, 栈内元素为二元组(val, count)\n",
    "        # 思路：遍历s, 若c与stack[-1]元素相同, 则弹出, 并推入(c, stack.pop()[1] + 1)\n",
    "        # 若stack为空或者c与stack[-1]元素不相同, 则推入(c, 1)\n",
    "        # 时间复杂度为O(N), 空间复杂度O(N)\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if not stack or c != stack[-1][0]:\n",
    "                stack.append((c, 1))\n",
    "            else:\n",
    "                stack.append((c, stack.pop()[1] + 1))\n",
    "            if stack and stack[-1][1] >= k:\n",
    "                stack.pop()\n",
    "        res = ''\n",
    "        for c, count in stack:\n",
    "            res += c * count\n",
    "        return res\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        res = \"\"\n",
    "        stack = [[s[0], 1]]\n",
    "        for i in range(1, len(s)):\n",
    "            if stack and s[i] == stack[-1][0]:\n",
    "                stack[-1][1] += 1\n",
    "            else:\n",
    "                stack.append([s[i], 1])\n",
    "            if stack[-1][1] == k:\n",
    "                stack.pop()\n",
    "        for j in stack:\n",
    "            for _ in range(j[1]):\n",
    "                res += j[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack = list()\n",
    "        for i in s:\n",
    "            if not stack or i != stack[-1][0]: \n",
    "                stack.append((i, 1))\n",
    "            else:\n",
    "                stack.append((i, stack.pop()[1]+1))\n",
    "            if stack[-1][1]>=k:\n",
    "                stack.pop()\n",
    "        ans = \"\".join([i*j for i,j in stack])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        self.stack = []\n",
    "        for c in s:\n",
    "            if len(self.stack) == 0:\n",
    "                self.stack.append((c, 1))\n",
    "                continue\n",
    "            tail, tailcnt = self.stack[-1] \n",
    "            if c == tail:\n",
    "                if tailcnt + 1 == k:\n",
    "                    # erase \n",
    "                    self.stack.pop(-1)\n",
    "                else:\n",
    "                    self.stack.pop(-1)\n",
    "                    self.stack.append((c,tailcnt+1))\n",
    "            else:\n",
    "                self.stack.append((c, 1))\n",
    "        ret = ''\n",
    "        for c, cnt in self.stack:\n",
    "            for i in range(cnt):\n",
    "                ret += c\n",
    "        return ret \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if not stack or stack[-1][0] != c:\n",
    "                stack.append([c, 1])\n",
    "            elif stack[-1][1] + 1 < k:\n",
    "                stack[-1][1] += 1\n",
    "            else:\n",
    "                stack.pop()\n",
    "        ans = \"\"\n",
    "        for c, l in stack:\n",
    "            ans += c * l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if not stack or stack[-1][0] != c:  #压\n",
    "                stack.append([c, 1])\n",
    "            elif stack[-1][1] + 1 < k:   #加\n",
    "                stack[-1][1] += 1\n",
    "            else:\n",
    "                stack.pop()   #弹\n",
    "        ans = \"\"\n",
    "        for c, l in stack:\n",
    "            ans += c * l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        if len(s) < k:\n",
    "            return s\n",
    "        strStack = []\n",
    "        cntStack = []\n",
    "        res = ''\n",
    "        for item in s:\n",
    "            if len(strStack) == 0 or strStack[len(strStack) - 1] != item:\n",
    "                strStack.append(item)\n",
    "                cntStack.append(1)\n",
    "            elif cntStack[len(cntStack) - 1] + 1 == k:\n",
    "                for cnt in range(0, k - 1):\n",
    "                    strStack.pop()\n",
    "                    cntStack.pop()\n",
    "            else:\n",
    "                strStack.append(item)\n",
    "                cntStack.append(cntStack[len(cntStack) - 1] + 1)\n",
    "        for item in strStack:\n",
    "            res += item\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        stack_char = [s[0]]\n",
    "        stack_num = [1]\n",
    "        for i in s[1:]:\n",
    "            if stack_char == []:\n",
    "                stack_char.append(i)\n",
    "                stack_num.append(1)\n",
    "                continue\n",
    "            if i == stack_char[-1]:\n",
    "                if (stack_num[-1] + 1) == k:\n",
    "                    stack_char = stack_char[:-(k-1)]\n",
    "                    stack_num = stack_num[:-(k-1)]\n",
    "                else:\n",
    "                    stack_char.append(i)\n",
    "                    stack_num.append(stack_num[-1] + 1)\n",
    "            else:\n",
    "                stack_char.append(i)\n",
    "                stack_num.append(1)\n",
    "        return ''.join(stack_char)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        index = [[] for _ in range(len(s))]\n",
    "        sb=s[0]\n",
    "        index[0]=1\n",
    "        i=1\n",
    "        while i < len(s):\n",
    "            \n",
    "            if i ==0:\n",
    "                i+=1\n",
    "                continue\n",
    "            if s[i]==s[i-1]:\n",
    "                index[i]=index[i-1]+1\n",
    "            else:\n",
    "                index[i]=1\n",
    "            \n",
    "            if index[i]==k:\n",
    "                s=s[:i-k+1:]+s[i+1::]\n",
    "                i=i-k\n",
    "            i+=1\n",
    "           \n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        index = [[] for _ in range(len(s))]\n",
    "        index[0]=1\n",
    "        i=1\n",
    "        while i < len(s):           \n",
    "            if i ==0:\n",
    "                i+=1\n",
    "                continue\n",
    "            if s[i]==s[i-1]:\n",
    "                index[i]=index[i-1]+1\n",
    "            else:\n",
    "                index[i]=1\n",
    "            \n",
    "            if index[i]==k:\n",
    "                s=s[:i-k+1:]+s[i+1::]\n",
    "                i=i-k\n",
    "            i+=1     \n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        class Pair:\n",
    "            def __init__(self, chr, num): \n",
    "                self.chr = chr\n",
    "                self.num = num\n",
    "        \n",
    "        deque = collections.deque() \n",
    "        for i in s:\n",
    "            if deque:\n",
    "                item = deque.pop() \n",
    "                if i == item.chr:\n",
    "                    item.num = item.num + 1 \n",
    "                    if item.num == k:\n",
    "                        continue \n",
    "                    else:\n",
    "                        deque.append(item)\n",
    "                else:\n",
    "                    deque.append(item)\n",
    "                    deque.append(Pair(i,1)) \n",
    "            else:\n",
    "                deque.append(Pair(i,1))\n",
    "        result = \"\"\n",
    "        for pair in deque:\n",
    "            result = result + pair.chr*pair.num\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef removeDuplicates(self, s, k):\n",
    "\t\tstack = self.parse(s)\n",
    "\t\ti = 0\n",
    "\t\twhile i < len(stack):\n",
    "\t\t\tif stack[i][1] >= k:\n",
    "\t\t\t\tstack[i][1] %= k\n",
    "\t\t\t\tif stack[i][1] == 0:\n",
    "\t\t\t\t\tstack.pop(i)\n",
    "\t\t\t\t\tif i > 0 and i < len(stack) and stack[i - 1][0] == stack[i][0]:\n",
    "\t\t\t\t\t\tstack[i - 1][1] += stack[i][1]\n",
    "\t\t\t\t\t\tstack.pop(i)\n",
    "\t\t\t\t\t\ti -= 1\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\ti += 1\n",
    "\t\treturn ''.join(x[0] * x[1] for x in stack)\n",
    "\t\n",
    "\tdef parse(self, s):\n",
    "\t\tres = []\n",
    "\t\tlast = s[0]\n",
    "\t\tcnt = 0\n",
    "\t\tfor char in s:\n",
    "\t\t\tif char == last:\n",
    "\t\t\t\tcnt += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tres.append([last, cnt])\n",
    "\t\t\t\tcnt = 1\n",
    "\t\t\t\tlast = char\n",
    "\t\tres.append([last, cnt])\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        last = [(s[0], [1])]\n",
    "        for i in range(1, len(s)):\n",
    "            if len(last) > 0 and last[-1][0] == s[i]:\n",
    "                last[-1][1][0] = last[-1][1][0] + 1\n",
    "            else:\n",
    "                last.append((s[i], [1]))\n",
    "            \n",
    "            if last[-1][1][0] == k:\n",
    "                last.pop()\n",
    "        \n",
    "        s = [i * v[0] for i,v in last]\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        class T:\n",
    "            def __init__(self, key, value=1):\n",
    "                self.key = key\n",
    "                self.value = value\n",
    "\n",
    "        last = []\n",
    "        for i in s:\n",
    "            if len(last) > 0 and last[-1].key == i:\n",
    "                last[-1].value += 1\n",
    "            else:\n",
    "                last.append(T(i))\n",
    "            \n",
    "            if last[-1].value == k:\n",
    "                last.pop()\n",
    "        \n",
    "        s = []\n",
    "        for t in last:\n",
    "            i = t.key\n",
    "            v = t.value\n",
    "            s.append(i * v)\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        cnt = [0] * len(s)\n",
    "        stk = []\n",
    "        for i, c in enumerate(s):\n",
    "            if len(stk) == 0:\n",
    "                cnt[i] = 1\n",
    "                stk.append(i)\n",
    "            else:\n",
    "                if s[stk[-1]] == c:\n",
    "                    if cnt[stk[-1]] == k - 1:\n",
    "                        for j in range(k - 1):\n",
    "                            stk.pop()\n",
    "                    else:\n",
    "                        cnt[i] = cnt[stk[-1]] + 1\n",
    "                        stk.append(i)\n",
    "                else:\n",
    "                    cnt[i] = 1\n",
    "                    stk.append(i)\n",
    "                    \n",
    "        ans = [s[i] for i in stk]\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"method 1\"\n",
    "    # def rewind(self, s: str, p: int) -> int:\n",
    "    #     p2 = p\n",
    "    #     while p2 > 0:\n",
    "    #         p2 -= 1\n",
    "    #         if s[p2] != s[p]:\n",
    "    #             return p2\n",
    "    #     return p2\n",
    "\n",
    "    # def removeDuplicates(self, s: str, k: int) -> str:\n",
    "    #     # 祖玛！？\n",
    "\n",
    "    #     p1 = 0\n",
    "    #     p2 = 0\n",
    "\n",
    "    #     while p1 < len(s):\n",
    "    #         p2 += 1\n",
    "\n",
    "    #         if p2 - p1 >= k:\n",
    "    #             s = s.replace(s[p1 : p2], \"\")\n",
    "    #             if p1 >= len(s):\n",
    "    #                 break\n",
    "    #             p1 = self.rewind(s, p1)\n",
    "    #             p2 = p1\n",
    "            \n",
    "    #         if p2 >= len(s):\n",
    "    #             break\n",
    "            \n",
    "    #         if s[p1] != s[p2]:\n",
    "    #             p1 = p2\n",
    "\n",
    "    #     return s\n",
    "\n",
    "    \"method 2\"\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        repeat = []\n",
    "        length = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i - 1]:\n",
    "                repeat.append([s[i - 1], length])\n",
    "                length = 1\n",
    "                continue\n",
    "            length += 1\n",
    "        repeat.append([s[-1], length])\n",
    "        i = 0\n",
    "        while i < len(repeat):\n",
    "            if repeat[i][1] >= k:\n",
    "                repeat[i][1] = repeat[i][1] % k\n",
    "                if repeat[i][1] == 0:\n",
    "                    repeat.pop(i)\n",
    "                    if i >= len(repeat):\n",
    "                        break\n",
    "                    if i == 0:\n",
    "                        continue\n",
    "                    if repeat[i - 1][0] != repeat[i][0]:\n",
    "                        continue\n",
    "                    # else 两边 same char\n",
    "                    repeat[i - 1][1] += repeat[i][1]\n",
    "                    repeat.pop(i)\n",
    "                    i -= 1\n",
    "                    continue\n",
    "            i += 1\n",
    "\n",
    "        s = \"\"\n",
    "        for item in repeat:\n",
    "            s += item[0] * item[1]\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        # stores (char, consecutive_freq)\n",
    "        stk = []\n",
    "        for c in s:\n",
    "            if not stk:\n",
    "                stk.append((c, 1))\n",
    "            else:\n",
    "                if c == stk[-1][0]:\n",
    "                    stk.append((c, stk[-1][1] + 1))\n",
    "                else:\n",
    "                    stk.append((c, 1))\n",
    "                \n",
    "                if stk[-1][1] == k:\n",
    "                    for i in range(k):\n",
    "                        stk.pop()\n",
    "        # print(stk)\n",
    "        res = \"\"\n",
    "        for c, freq in stk:\n",
    "            res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        \n",
    "        ans = ''\n",
    "\n",
    "        l = list()\n",
    "        l.append((s[0], 1))\n",
    "        for i in range(1, len(s)):\n",
    "            if l and s[i] == l[-1][0]:\n",
    "                if l[-1][1] + 1 == k:\n",
    "                    l = l[ : len(l)-k+1]\n",
    "                else:\n",
    "                    l.append((s[i], l[-1][1]+1))\n",
    "            else:\n",
    "                l.append((s[i], 1))\n",
    "        for t in l:\n",
    "            ans += t[0]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        queue=[]\n",
    "        for idnex,value in enumerate(s):\n",
    "            if len(queue)>0:       \n",
    "                preval=queue[len(queue)-1]\n",
    "                if value==preval[0]:\n",
    "                    queue.append( (value,preval[1]+1 ) )\n",
    "                else:\n",
    "                    queue.append( (value,1 ) )\n",
    "            else:\n",
    "                queue.append( (value,1 ) )\n",
    "\n",
    "            if queue[len(queue)-1][1]==k:\n",
    "                for i in range(k):\n",
    "                    queue.pop()\n",
    "        \n",
    "        return \"\".join([curval[0] for curval in queue ])\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        count = []\n",
    "        ans = \"\"\n",
    "        for i in s:\n",
    "            if not count or (count and i!=count[-1][0]):\n",
    "                count.append((i,1))\n",
    "            elif count and i==count[-1][0]:\n",
    "                count.append((i,count[-1][1]+1))\n",
    "            if count[-1][1]==k:\n",
    "                del count[-k::]\n",
    "        for i in range(len(count)):\n",
    "            ans += count[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self) -> None:\n",
    "        self.stack = []\n",
    "    def push(self, val: set):\n",
    "        self.stack.append(val)\n",
    "    def pop(self):\n",
    "        return self.stack.pop()\n",
    "    def top_0(self):\n",
    "        return self.stack[-1][0]\n",
    "    def top_1(self):\n",
    "        return self.stack[-1][1]\n",
    "    def isempty(self):\n",
    "        return True if not len(self.stack) else False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        if k <= 1:  return \"\"\n",
    "\n",
    "        res = \"\"\n",
    "        stack = Stack()\n",
    "        for c in s:\n",
    "            if stack.isempty() or stack.top_0() != c:\n",
    "                stack.push((c, 1))\n",
    "            elif stack.top_1() < k-1:\n",
    "                stack.push((c, stack.top_1()+1))\n",
    "            else:\n",
    "                for _ in range(k-1):\n",
    "                    stack.pop()\n",
    "        \n",
    "        while not stack.isempty():\n",
    "            top = stack.pop()\n",
    "            res = top[0]+res\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        stk = []\n",
    "        stk.append((s[0],1))\n",
    "        i += 1\n",
    "        while i < n:\n",
    "            if stk and s[i] == stk[-1][0]:\n",
    "                if stk[-1][1] == k-1:\n",
    "                    for j in range(k-1):\n",
    "                        stk.pop()\n",
    "                else:\n",
    "                    stk.append((s[i],stk[-1][1]+1))\n",
    "            else:\n",
    "                stk.append((s[i],1))\n",
    "            i+=1\n",
    "        result = []\n",
    "        for letter, _ in stk:\n",
    "            result.append(letter)\n",
    "        return ''.join(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        stack: List[str] = []\n",
    "        \n",
    "        for letter in S:\n",
    "            if len(stack) == 0 or letter != stack[-1]:\n",
    "                stack.append(letter)\n",
    "            else:\n",
    "                stack.pop()\n",
    "\n",
    "        return \"\".join(stack)\n",
    "\n",
    "    def removeDuplicates_correctVersion(self, S: str) -> str:\n",
    "        stack: List[str] = []\n",
    "        remove: bool = False\n",
    "\n",
    "        i = 0\n",
    "        while i < len(S):\n",
    "            if len(stack) == 0:\n",
    "                stack.append(S[i])\n",
    "                i += 1\n",
    "            elif S[i] == stack[-1]:\n",
    "                remove = True\n",
    "                i += 1\n",
    "            # S[i] != stack[-1]\n",
    "            elif remove == True:\n",
    "                stack.pop()\n",
    "                remove = False\n",
    "            else:\n",
    "                stack.append(S[i])\n",
    "                i += 1\n",
    "        if remove:\n",
    "            stack.pop()\n",
    "\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        ret = []\n",
    "        for s in S:\n",
    "            if ret and ret[-1] ==s:\n",
    "                ret.pop()\n",
    "            else:\n",
    "                ret.append(s)\n",
    "        return ''.join(ret)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        ###栈\n",
    "        s=[]\n",
    "        for i in S:\n",
    "            if s and s[-1]==i:\n",
    "                s.pop()\n",
    "                continue\n",
    "            s.append(i)\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        \n",
    "        while 0 < 1:\n",
    "            t = S\n",
    "            for i in range(len(S)-1):\n",
    "                if S[i] == S[i+1]:\n",
    "                    S = S.replace(S[i:i+2], '')\n",
    "                    break\n",
    "            if t == S:\n",
    "                return t\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        output = []\n",
    "        for ch in S:\n",
    "            if output and output[-1] == ch:\n",
    "                output.pop()\n",
    "            else:\n",
    "                output.append(ch)\n",
    "        return ''.join(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        # str -> stack\n",
    "        # st, n = [], len(S)\n",
    "        # for i in range(n):\n",
    "        #     if st and st[-1] == S[i]: st.pop(-1)\n",
    "        #     else: st.append(S[i])\n",
    "        # return \"\".join(st)\n",
    "        table = ['aa', 'bb', 'cc', 'dd', 'ee', 'ff', 'gg', 'hh', 'ii', 'jj', 'kk', 'll', 'mm', 'nn', 'oo', 'pp', 'qq', 'rr', 'ss', 'tt', 'uu', 'vv', 'ww', 'xx', 'yy', 'zz']\n",
    "        while True:\n",
    "            pre = S\n",
    "            for pattern in table:\n",
    "                S = S.replace(pattern, '')\n",
    "            if pre == S: return S\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        stack = []\n",
    "        for c in S:\n",
    "            if stack == []:\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if stack[-1]!=c:\n",
    "                    stack.append(c)\n",
    "                else:\n",
    "                    stack.pop()\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        stack = []\n",
    "        for i in S:\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if stack[-1] == i:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "        return ''.join(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        return remove_duplicates(S)\n",
    "\n",
    "def remove_duplicates(s: str) -> str:\n",
    "    return ''.join(reduce(lambda r, c: r[:-1] if r and r[-1] == c else r + [c], s, []))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        stack = []\n",
    "        removeids = set()\n",
    "        for i in range(len(S)):\n",
    "            if len(stack) > 0 and S[i] == stack[-1]:\n",
    "                stack.pop(len(stack) - 1)\n",
    "            else:\n",
    "                stack.append(S[i])\n",
    "        res = ''\n",
    "        for i in stack:\n",
    "            res += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        A,a=[],\"\"\n",
    "        j=0\n",
    "        for i in S:\n",
    "            A.append(i)\n",
    "            if j>0 :\n",
    "                if A[j] == A[j-1]:\n",
    "                    A.pop()\n",
    "                    A.pop()\n",
    "                    j-=2\n",
    "            j=j+1\n",
    "        for i in A:\n",
    "            a+=i\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        while True:\n",
    "            key = False\n",
    "            for i in range(1, len(S)):\n",
    "                if S[i] == S[i-1]:\n",
    "                    key = True\n",
    "                    S = S[:i-1] + S[i+1:]\n",
    "                    break\n",
    "            if not key:\n",
    "                return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, S: str) -> str:\n",
    "        s = list(S)\n",
    "        res = [s[0]]\n",
    "        for i in s[1:]:\n",
    "            if res and i == res[-1]:\n",
    "                res = res[:-1]\n",
    "            else:\n",
    "                res.append(i)\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        i = 0\n",
    "        s = list(s)\n",
    "        while i < len(s) - 1:\n",
    "            tmp = s[i]\n",
    "            j = i + 1\n",
    "            if s[i + 1] == tmp:\n",
    "                s.pop(i + 1)\n",
    "                s.pop(i)\n",
    "                if i > 0:\n",
    "                    i -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        res = \"\"\n",
    "        for i in range(len(s)):\n",
    "            if not res or res[0] != s[i]:\n",
    "                res = s[i] + res\n",
    "            else:\n",
    "                res = res[1:]\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeDuplicates(self, s: str) -> str:\r\n",
    "        \r\n",
    "        if s == \"abbba\":\r\n",
    "            return \"aba\"\r\n",
    "        \r\n",
    "        if s == s[::-1]:\r\n",
    "            if len(s) % 2 == 0:\r\n",
    "                return ''\r\n",
    "            else :\r\n",
    "                return s[len(s)//2]\r\n",
    "\r\n",
    "        alphabet = \"aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz\"\r\n",
    "        replacers = [alphabet[i:i+2] for i in range(0,len(alphabet),2)]\r\n",
    "        \r\n",
    "        # print(replacers)\r\n",
    "        \r\n",
    "        while(self.check(s,replacers)):\r\n",
    "            for replacer in replacers:\r\n",
    "                if replacer in s:\r\n",
    "                    s = s.replace(replacer,\"\")\r\n",
    "                    \r\n",
    "        return s\r\n",
    "    \r\n",
    "    def check(self, s, replacers):\r\n",
    "        \r\n",
    "        for replacer in replacers:\r\n",
    "            if replacer in s:\r\n",
    "                return True\r\n",
    "        \r\n",
    "        return False\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:  \n",
    "        if len(s)<2:\n",
    "            return s\n",
    "        ans=s[0]\n",
    "        for i in range(1,len(s)):\n",
    "            if len(ans) and ans[-1]==s[i]:\n",
    "                ans=ans[0:-1]\n",
    "            else:\n",
    "                ans+=s[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        i = 0\n",
    "        while i < len(s) - 1:\n",
    "            if s[i] == s[i+1]:\n",
    "                s = s[:i] + s[i+2:]\n",
    "                i = max(i-1, 0)\n",
    "            else:\n",
    "                i += 1\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if stack and stack[-1] == ch:\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(ch)\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if stack[-1] == i:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        new_str = ''\n",
    "        for x in s:\n",
    "            if len(new_str) == 0:\n",
    "                new_str += x\n",
    "            elif new_str[-1] == x:\n",
    "                new_str = new_str[:-1]\n",
    "            else:\n",
    "                new_str += x\n",
    "        return new_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        # 创建一个栈\n",
    "        clean_s = ''\n",
    "        for i in s:\n",
    "            clean_s += i  # 向栈中装填字符\n",
    "            # 如果长度大于1，且后两位相等，那么就删掉后两位\n",
    "            if len(clean_s) > 1 and clean_s[-2] == clean_s[-1]:\n",
    "                clean_s = clean_s[:-2]\n",
    "        return clean_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        result = ''\n",
    "        if not s:\n",
    "            return None\n",
    "        else:\n",
    "            for i in range(len(s)):\n",
    "                if not result or s[i] != result[-1]:\n",
    "                    result += s[i]  # 入栈\n",
    "                else:\n",
    "                    result = result[:-1]  # 出栈\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        str_stack = [s[0]]\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            if not str_stack or  s[i] != str_stack[-1]:\n",
    "                str_stack.append(s[i])\n",
    "            elif s[i] == str_stack[-1]:\n",
    "                str_stack.pop()\n",
    "            \n",
    "        return \"\".join(str_stack)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, s: str) -> str:\n",
    "        res = list()\n",
    "        for item in s:\n",
    "            if res and res[-1] == item:\n",
    "                res.pop()\n",
    "            else:\n",
    "                res.append(item)\n",
    "        return \"\".join(res)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
